﻿#pragma once
#include "Index.h"

class IPeakIndexInMountainArray
{
public:
	/**
	 * 山峰数组的峰顶索引.
	 * https://leetcode.cn/problems/peak-index-in-a-mountain-array
	 * 数组 二分查找
	 *
	 * 符合下列属性的数组 arr 称为 山脉数组 ：
	 * arr.length >= 3
	 * 存在 i（0 < i < arr.length - 1）使得：
	 *	arr[0] < arr[1] < ... arr[i-1] < arr[i]
	 *  arr[i] > arr[i+1] > ... > arr[arr.length - 1]
	 * 给你由整数组成的山脉数组 arr ，返回任何满足的下标 i 。
	 *
	 * 注意:头目数据arr保证是一个山峰数组
	 */
	virtual int peakIndexInMountainArray(std::vector<int>& arr) = 0;
};

class PeakIndexInMountainArray
{
public:
	class Solution:public IPeakIndexInMountainArray
	{
	public:
		int peakIndexInMountainArray(std::vector<int>& arr) override
		{
			const int arrSize = arr.size();

			int resultIndex = -1;
			if (arrSize < 3)
				return resultIndex;

			int left = 1, right = arrSize - 2;
			while (left <= right)
			{
				const int mid = left + ((right - left) >> 1);
				if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])
				{
					resultIndex = mid;
					break;
				}

				if (arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1])
					left = mid + 1;
				else if (arr[mid] > arr[mid + 1] && arr[mid] < arr[mid - 1])
					right = mid - 1;
				/*else
					EV_NOT_REACH_HERE;*/
			}
			return resultIndex;
		}
	};
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
TEST(PeakIndexInMountainArrayTest, peakIndexInMountainArray)
{
	TEST_SOLUTION1(IPeakIndexInMountainArray, PeakIndexInMountainArray::Solution, &)
	{
		__slnTestor.setTestTimes(100);

		constexpr int numsSize = 100;
		std::vector<int> nums;
		int peakIndex;

		nums = TestingUtil::randUniqueRangeInts(numsSize, 0, 1000);
		std::sort(nums.begin(), nums.end());

		do
		{
			peakIndex = TestingUtil::randIndexInSize(numsSize);
		} while (peakIndex == 0 || peakIndex == numsSize - 1);
		std::reverse(nums.begin() + peakIndex, nums.end());

		const auto resultIndex= solution->peakIndexInMountainArray(nums);

		EXPECT_EQ(resultIndex, peakIndex);

		if(HasFailure())
		{
			std::cout << "---------------" << std::endl
				<< "Nums=" << FormatedUtil::dumpFormated(nums) << std::endl;
		}
	};
}
#endif